package main

import "fmt"

/**
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

思路:

设最长回文子串的起始位置是start，长度是length。并用二维数组m做备忘录存储，备忘录元素m[x][y]分别表示起始位置为x，结束位置为y的子串是否是回文串
如何判定字符串是回文串: 如果字符串首尾字符相同且其子串也是回文字符串，那么这个字符串就是回文字符串。
如果长度为1，开始结束字符相同，符合上述判断仿佛，所以一定是回文子串
如果长度是2，如果开始和结束字符相同，则为回文字符串，否则不是
如果长度大于3，则需要依靠判定方法判定首尾字符，再根据备忘录查找子串是否是回文字符串
举个例子，字符串为s，起始位置为i,字符串长度为j，翻译下判定方法就是s[i] == s[i+j-1] && m[i+1][i+j-2]
利用动态规划

	状态字典是m[x][y]
	状态转移方程就是
			长度等于1
			长度等于2
			长度大于等于3 s[i] == s[i+j-1] && m[i+1][i+j-2]

这样就覆盖到了所有长度的子字符串
https://www.bilibili.com/video/av10327204
*/

func longestPalindrome(s string) string {
	l := len(s)
	if l < 2 {
		return s
	}
	m := generateBoolArray(l, l)
	start := 0 // start,length记录最长回文子串起始位置和长度
	length := 1

	// 先对长度为1的情况做处理
	for i := 0; i < l; i++ {
		m[i][i] = true
	}

	// 再对长度为2的情况做处理
	for i := 0; i < l-1; i++ { // i+j<l
		if s[i] == s[i+1] {
			m[i][i+1] = true
			start = i
			length = 2
		}
	}

	// 注意: 双重循环一定要长度变量j是最外层 按长度来一级一级推进 因为内部m[i+1][i+j-2]判断是依赖上一层的结果的
	// 对长度为3的情况做处理 j表示长度 范围为3<=j<=l
	// 起始位置为i，长度为j的子串，最后一位索引位置是i+j-1
	/**
	对于71行等号的理解
	1 2 3 4 5
	a b c d e
	字符总长度是l，最后一个字符的索引是l-1,倒数第k个元素的索引是l-k 或 l-1-k+1
	字符总长度是5，最后一个字符的索引是4,倒数第3个元素的索引是5-3=2 或 4-3+1
	*/
	for j := 3; j <= l; j++ { // j为子序列长度
		for i := 0; i <= l-j; i++ { // i+j < l 比如i=0,j=5 l=5 最大i+j=l
			if s[i] == s[i+j-1] && m[i+1][i+j-2] {
				m[i][i+j-1] = true
				start = i
				length = j
			}
		}
	}

	return s[start : start+length] //注意这里是start+length
}

func generateBoolArray(x, y int) [][]bool {
	m := [][]bool{}
	for i := 0; i < x; i++ {
		m = append(m, make([]bool, y))
	}
	return m
}

func main() {
	fmt.Println(longestPalindrome("aaaaa"))
}
